// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
#include<stack>
using namespace std;

 struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


// Solution 1:先遍历一遍取得链表长度，再确定删除节点的正向位置
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len = 0;
        ListNode * L = head;
        while (L != nullptr)
        {
            ++len;
            L = L->next;
        }

        // 因为存在只有一个节点的链表要删除唯一的节点，所以要new一个多一个头节点的新链表，否则无法删除
        ListNode * tmp = new ListNode(0,head);
        ListNode * cur = tmp;
        for(int i=1; i < len-n+1; ++i){
            cur = cur->next;
        }
        cur->next = cur->next->next;
        
        ListNode * ans = tmp->next;
        delete tmp;
        return ans;
    }
};

// 在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 nn 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

// 双指针：使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 n个节点。
// 当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n个节点。
// 初始时 first 和 second 均指向头节点。首先使用 first 对链表进行遍历，遍历n步.此时，first 和 second 之间间隔了 n-1个节点，即 first 比 second 超前了 n个节点。
// 之后同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾时，second 恰好指向倒数第 n个节点。
// 如果我们能够得到的是倒数第 n个节点的前驱节点而不是倒数第 n个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点
// 这样一来，当 first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};
